﻿// homework3_1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <tchar.h>
#include <stack>
#include <utility>
#include <iostream>
#include <sstream>
#include <queue>
#include <cmath>
#include <list>
using namespace std;


//二叉树结点类
template<class T>
class BinaryTreeNode
{
private:
	T value;
	BinaryTreeNode<T> *leftChild;
	BinaryTreeNode<T> *rightChild;
public:
	BinaryTreeNode() { leftChild = NULL, rightChild = NULL; };
	BinaryTreeNode(const T&mValue);
	BinaryTreeNode(const T&mValue, BinaryTreeNode<T> *mLeftChild, BinaryTreeNode *mRightChild);

	void setValue(const T&mValue);
	T getValue()const;

	BinaryTreeNode<T> * getLeftChild()const;
	BinaryTreeNode<T> * getRightChild()const;
	void setLeftChild(BinaryTreeNode<T> *leftChild);
	void setRightChild(BinaryTreeNode<T> *rightChild);

	bool isLeaf()const;
};
template<class T>
BinaryTreeNode<T>::BinaryTreeNode(const T&mValue)
{
	value = mValue;
	leftChild = rightChild = NULL;
}

template<class T>
BinaryTreeNode<T>::BinaryTreeNode(const T&mValue, BinaryTreeNode<T> *mLeftChild, BinaryTreeNode *mRightChild)
{
	value = mValue;
	leftChild = mLeftChild;
	rightChild = mRightChild;
}

template<class T>
T BinaryTreeNode<T>::getValue()const//得到该结点的值
{
	return value;
}

template<class T>
BinaryTreeNode<T>* BinaryTreeNode<T>::getLeftChild()const//得到左子结点
{
	return leftChild;
}

template<class T>
BinaryTreeNode<T>* BinaryTreeNode<T>::getRightChild()const//得到右子结点
{
	return rightChild;
}

template<class T>
void BinaryTreeNode<T>::setLeftChild(BinaryTreeNode<T> *leftChild)//设置左子结点
{
	this->leftChild = leftChild;
}

template<class T>
void BinaryTreeNode<T>::setRightChild(BinaryTreeNode<T> *rightChild)//设置右子结点
{
	this->rightChild = rightChild;
}

template<class T>
void BinaryTreeNode<T>::setValue(const T&mValue)//设置该结点的值
{
	value = mValue;
}

template<class T>
bool BinaryTreeNode<T>::isLeaf()const//是否为树叶
{
	return leftChild == NULL && rightChild == NULL;
}

class ExpressionBinaryTree
{
private:
	BinaryTreeNode<string> *root;
	void clear()
	{
		if (root == NULL)
			return;
		recursionDeleteAll(root);
	};//调用内部递归函数清空二叉树，以及释放空间
	bool aIsGreaterOrEqualThanB(char a, char b);//工具方法，用于比较a,b优先级
	int getHeight(BinaryTreeNode<string> *root);//求树的高度
	void printBlank(int n);//工具方法，打印n个空格
	void printInRightFormat(string value);//按照格式打印，以便对齐
	void recursionPrintPreffixE(BinaryTreeNode<string> *root);//递归调用打印前缀表达式
	void recursionPrintSuffixE(BinaryTreeNode<string> *root);//递归调用打印后缀表达式
	bool shouldPrintLeftBracket(const stack<BinaryTreeNode<string>*> &nodeStack, BinaryTreeNode<string> *pointer, int leftOrRight);//用于输出中缀表达式时判断是否需要输出左括号
	void recursionDeleteAll(BinaryTreeNode<string> *root);
public:
	ExpressionBinaryTree() { root = NULL; };
	~ExpressionBinaryTree() { clear(); };
	void buildBTreeByPreffixE();//以前缀表达式构建二叉树
	void buildBTreeByInfixE();//以中缀表达式构建二叉树
	void buildBTreeBySuffixE();//以后缀表达式构建二叉树
	void printEBTree();//打印二叉树字符图
	void printPreffixE() { recursionPrintPreffixE(root); cout << endl; }//将递归调用封装，只留给用户打印接口
	void printSuffixE() { recursionPrintSuffixE(root); cout << endl; }//将递归调用封装，只留给用户打印接口
	void printInfixE();
	static const int LEFT = 0;//为左子结点
	static const int RIGHT = 1;//为右子结点

};

bool ExpressionBinaryTree::aIsGreaterOrEqualThanB(char a, char b)
{
	switch (a)
	{
	case '*':
	case '/':
		return true;
	case '+':
	case '-':
		if (b == '*' || b == '/')
			return false;
		return true;
	case '(':
		return false;
	}
	return false;
}

int ExpressionBinaryTree::getHeight(BinaryTreeNode<string> *root)//求树的高度
{
	if (root == NULL)
		return 0;
	int left = getHeight(root->getLeftChild());
	int right = getHeight(root->getRightChild());
	return left > right ? left + 1 : right + 1;
}

void ExpressionBinaryTree::printBlank(int n)
{
	for (int i = 0; i < n; ++i)
		cout << " ";
}

void ExpressionBinaryTree::printInRightFormat(string value)//按照格式打印，以便对齐
{
	switch (value.length())
	{
	case 1://如果就1个字符，则在两端打印空格，以便对齐
		cout << " ";
		cout << value << " ";
		break;
	case 2://如果2个字符，则在其后补一个空格，以便对齐
		cout << value << " ";
		break;
	case 3:
		cout << value;//如果3个字符，则不用补空格
		break;
	}
}

void ExpressionBinaryTree::recursionPrintPreffixE(BinaryTreeNode<string> * root)//递归调用打印前缀表达式
{
	if (root == NULL)
		return;
	cout << root->getValue() << "";
	recursionPrintPreffixE(root->getLeftChild());
	recursionPrintPreffixE(root->getRightChild());
}

void ExpressionBinaryTree::recursionPrintSuffixE(BinaryTreeNode<string> * root)//递归调用打印后缀表达式
{
	if (root == NULL)
		return;
	recursionPrintSuffixE(root->getLeftChild());
	recursionPrintSuffixE(root->getRightChild());
	cout << root->getValue() << "";
}

bool ExpressionBinaryTree::shouldPrintLeftBracket(const stack<BinaryTreeNode<string> *> &nodeStack, BinaryTreeNode<string> *pointer, int leftOrRight)//是否应该添加左括号
{
	if (nodeStack.empty())
		return false;
	if (pointer == NULL)
		return false;
	char a = nodeStack.top()->getValue().c_str()[0];//a b 为栈中父子关系的两个结点值得首字母(为了区分是数字还是操作符)
	char b = pointer->getValue().c_str()[0];
	if (b >= '0' && b <= '9')//如果是数字，则不用打括号
		return false;
	if (leftOrRight == LEFT)//如果pointer是左结点
	{
		switch (a)
		{
		case '*':
		case '/':
			if (b == '*' || b == '/')
				return false;
			return true;
		case '+':
		case '-':
			return false;
		}
	}
	else if (leftOrRight == RIGHT)//如果pointer是右结点
	{
		switch (a)
		{
		case '*':
		case '/':
			return true;
		case '+':
		case '-':
			if (b == '+' || b == '-')
				return true;
			return false;
		}
	}
	return false;
}

void ExpressionBinaryTree::recursionDeleteAll(BinaryTreeNode<string> *root)
{
	if (root->getLeftChild() != NULL)
		recursionDeleteAll(root->getLeftChild());
	if (root->getRightChild() != NULL)
		recursionDeleteAll(root->getRightChild());
	delete root;
}

void ExpressionBinaryTree::buildBTreeByPreffixE()
{
	clear();
	root = new BinaryTreeNode<string>();
	char c;
	//cout << "输入前缀表达式以=结尾:" << endl;
	//cout << "->:";
	cin >> c;
	stack<BinaryTreeNode<string> *> parentStack;//用于保存存放父结点
	BinaryTreeNode<string> *pointer = root;//用于指向下一个保存数据的结点
	string blankStr = "";
	double tempDouble = 0;
	string tempStr;//用于输入流，将浮点数转换成字符串
	while (c != '=')
	{
		switch (c)
		{
		case '+':
		case '-':
		case '*':
		case '/':
			pointer->setValue(c + blankStr);//设置当前结点的值
			pointer->setLeftChild(new BinaryTreeNode<string>());//生成左结点
			parentStack.push(pointer);
			pointer = pointer->getLeftChild();
			break;
		default:
			cin.putback(c);
			cin >> tempDouble;
			stringstream sss;
			sss << tempDouble;
			sss >> tempStr;
			pointer->setValue(tempStr);

			pointer = parentStack.top();
			while (pointer->getRightChild() != NULL)
			{
				parentStack.pop();//找到按前序遍历的下一个结点
				if (parentStack.empty())
					break;
				pointer = parentStack.top();
			}
			if (parentStack.empty())//如果此时栈空则表明表达式已经构建完成
				break;
			pointer->setRightChild(new BinaryTreeNode<string>());//找到了按前序遍历的下一个结点位置并生成结点
			pointer = pointer->getRightChild();
			break;
		}
		cin >> c;
	}

}

void ExpressionBinaryTree::buildBTreeByInfixE()//构造中缀表达式二叉树
{
	clear();
	root = new BinaryTreeNode<string>();
	char c;
	//cout << "输入中缀表达式以=结尾:" << endl;
	//cout << "->:";
	cin >> c;
	stack<BinaryTreeNode<string> *> opd;//操作数栈 //为了方便统一管理，操作数和操作符全部定义为string类型
	stack<string> opt;//操作符栈
	double tempDouble = 0;
	string tempStr;//用于输入流，将浮点数转换成字符串
	string blankStr = "";
	while (c != '=')
	{
		switch (c)
		{
		case '+':
		case '-':
		case '*':
		case '/':
			while (!opt.empty() && aIsGreaterOrEqualThanB(opt.top().c_str()[0], c))//如果栈顶操作符优先级高于读入操作符优先级，则表名应该先计算栈顶操作符
			{
				BinaryTreeNode<string> *secondOpd = opd.top();
				opd.pop();
				BinaryTreeNode<string> *firstOpd = opd.top();
				opd.pop();//从操作数栈取出两个操作数
				opd.push(new BinaryTreeNode<string>(opt.top(), firstOpd, secondOpd));//将操作数和操作符组成一个新结点存入栈中
				opt.pop();
			}
			opt.push(c + blankStr);//将读入操作符入栈
			break;
		case '(':
			opt.push(c + blankStr);//遇到左括号直接入栈
			break;
		case ')':
			while (!opd.empty() && opt.top().c_str()[0] != '(')//为了防止冗赘括号，但未检测括号不匹配
			{
				BinaryTreeNode<string> *secondOpd = opd.top();
				opd.pop();
				BinaryTreeNode<string> *firstOpd = opd.top();
				opd.pop();//从操作数栈取出两个操作数
				opd.push(new BinaryTreeNode<string>(opt.top(), firstOpd, secondOpd));//将操作数和操作符组成一个新结点存入栈中
				opt.pop();
			}
			opt.pop();//将左括号出栈
			break;
		default://如果是操作数，直接包装成结点入栈
			cin.putback(c);
			cin >> tempDouble;
			stringstream sss;
			sss << tempDouble;
			sss >> tempStr;
			opd.push(new BinaryTreeNode<string>(tempStr));
			break;
		}
		cin >> c;
	}
	while (!opt.empty() && aIsGreaterOrEqualThanB(opt.top().c_str()[0], c))//如果栈顶操作符优先级高于读入操作符优先级，则表名应该先计算栈顶操作符
	{
		BinaryTreeNode<string> *secondOpd = opd.top();
		opd.pop();
		BinaryTreeNode<string> *firstOpd = opd.top();
		opd.pop();//从操作数栈取出两个操作数
		opd.push(new BinaryTreeNode<string>(opt.top(), firstOpd, secondOpd));//将操作数和操作符组成一个新结点存入栈中
		opt.pop();
	}
	root = opd.top();//此时操作数栈中唯一元素即为根元素
	opd.pop();
}

void ExpressionBinaryTree::buildBTreeBySuffixE()
{
	clear();
	char c;
	//cout << "输入后缀表达式以=结尾:" << endl;
	//cout << "->:";
	cin >> c;
	stack<BinaryTreeNode<string> *> opdStack;//抽象意义上为操作数栈，但实际为操作数和操作符构成的结点栈
	double tempDouble = 0;
	string tempStr;//用于输入流，将浮点数转换成字符串
	string blankStr = "";
	while (c != '=')
	{
		switch (c)
		{
		case '+':
		case '-':
		case '*':
		case '/':
		{
			BinaryTreeNode<string> *secondOpd = opdStack.top();
			opdStack.pop();
			BinaryTreeNode<string> *firstOpd = opdStack.top();
			opdStack.pop();
			opdStack.push(new BinaryTreeNode<string>(c + blankStr, firstOpd, secondOpd));
			break;
		}
		default:
			cin.putback(c);
			cin >> tempDouble;
			stringstream sss;
			sss << tempDouble;
			sss >> tempStr;
			opdStack.push(new BinaryTreeNode<string>(tempStr));
			break;
		}
		cin >> c;
	}
	root = opdStack.top();//此时操作数栈中唯一元素即为根元素
	opdStack.pop();
}

void ExpressionBinaryTree::printEBTree()
{
	int height = getHeight(root);
	int headIndentation;//行首缩进空格数
	int InIndentation;//行中单位数据间隔空格数
	queue<BinaryTreeNode<string> *> nodeQueue;//结点队列
	nodeQueue.push(root);//将根结点入队列以便第一次操作
	BinaryTreeNode<string> *pointer;
	for (int i = 1; i <= height; ++i)
	{
		headIndentation = (int)2 * pow(2.0, double(height) - i) - 2;//根据层数获得行首缩进空格数
		printBlank(headIndentation);
		InIndentation = (int)2 * pow(2.0, double(height) - i + 1) - 3;//根据高度和层数计算行中单位数据间隔空格数
		for (int j = 0; j < pow(2.0, double(i) - 1) && !nodeQueue.empty(); ++j)//遍历第i层结点
		{
			pointer = nodeQueue.front();
			if (pointer == NULL)//如果是空，则直接输行中单位数据间隔空格数+3个空格(数据占3位，无数据则用空格补全)
			{
				printBlank(InIndentation + 3);
				nodeQueue.pop();
				nodeQueue.push(NULL);
				nodeQueue.push(NULL);//向队列内加入两个空子树，当作占位符，以便在无结点的地方输出空格
			}
			else
			{
				printInRightFormat(pointer->getValue());
				printBlank(InIndentation);
				nodeQueue.pop();
				nodeQueue.push(pointer->getLeftChild());//左右子树入队列
				nodeQueue.push(pointer->getRightChild());
			}
		}
		cout << endl;
	}
}

void ExpressionBinaryTree::printInfixE()
{
	stack<BinaryTreeNode<string> *> nodeStack;//结点栈，遍历使用
	BinaryTreeNode<string> *pointer = root;
	list<BinaryTreeNode<string> *> nodeList;//用于记录在哪些元素被输出之后要输出反括号
	while (!nodeStack.empty() || pointer != NULL)
	{
		while (pointer != NULL)//一直向左子结点走，找到左子结点时，经过的结点已全部入栈
		{
			if (shouldPrintLeftBracket(nodeStack, pointer, LEFT))//如果应该添加左括号,为左子结点的情况下
			{
				BinaryTreeNode<string> * temp = pointer->getRightChild();//找到应该在输出哪个结点后输出右括号
				while (temp->getRightChild() != NULL)
					temp = temp->getRightChild();
				nodeList.push_back(temp);//将该位置放入序列中，供查询使用
				cout << "(";
			}
			nodeStack.push(pointer);
			pointer = pointer->getLeftChild();
		}
		cout << nodeStack.top()->getValue();//输出结点 
		list<BinaryTreeNode<string> *>::iterator it = find(nodeList.begin(), nodeList.end(), nodeStack.top());
		while (it != nodeList.end())//若栈顶结点(即当前输出结点)为前面记录的应该输出右括号的结点时，输出右括号，可能有多个右括号需要输出，所以循环
		{
			cout << ")";
			nodeList.erase(it);
			it = find(nodeList.begin(), nodeList.end(), nodeStack.top());
		}
		pointer = nodeStack.top()->getRightChild();//所有左结点已经走完，向右走一个
		if (shouldPrintLeftBracket(nodeStack, pointer, RIGHT))//如果应该添加左括号,为右子结点的情况下
		{
			BinaryTreeNode<string> * temp = pointer->getRightChild();
			while (temp->getRightChild() != NULL)
				temp = temp->getRightChild();
			nodeList.push_back(temp);
			cout << "(";
		}
		nodeStack.pop();
	}
	cout << endl;
}

void printPrompting()//输出提示信息
{
	//cout << "\n1:前缀表达式.2:中缀表达式.3:后缀表达式:" ;
	//cout << ":";
}

int _tmain(int argc, _TCHAR* argv[])
{
	ExpressionBinaryTree ebt;
	char c;
	printPrompting();
	cin >> c;
	while (c != 'q')
	{
		switch (c)
		{
		case '1':
			ebt.buildBTreeByPreffixE();
		//	cout << "\n" << endl;
		//	cout << "二叉树为:" << endl;
			ebt.printEBTree();
			break;
		case '2':
			ebt.buildBTreeByInfixE();
		//	cout << "\n" << endl;
		//	cout << "二叉树为:" << endl;
			ebt.printEBTree();
			break;
		case '3':
			ebt.buildBTreeBySuffixE();
		//	cout << "\n" << endl;
		//	cout << "二叉树为:" << endl;
			ebt.printEBTree();
			break;
		}
		//cout << "->前缀表达式为:" << endl;
		//cout << "->";
		ebt.printPreffixE();
		//cout << "->中缀表达式为:" << endl;
		//cout << "->";
		ebt.printInfixE();
		//cout << "->后缀表达式为:" << endl;
		//cout << "->";
		ebt.printSuffixE();
		cout << "\n" << endl;
		printPrompting();
		cin >> c;
	}
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
